{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "ename": "ValueError",
     "evalue": "Invalid input: More than two unique differences found.",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mValueError\u001b[0m                                Traceback (most recent call last)",
      "Cell \u001b[1;32mIn[7], line 51\u001b[0m\n\u001b[0;32m     48\u001b[0m b \u001b[38;5;241m=\u001b[39m [\u001b[38;5;241m8\u001b[39m, \u001b[38;5;241m18\u001b[39m, \u001b[38;5;241m14\u001b[39m]\n\u001b[0;32m     49\u001b[0m c \u001b[38;5;241m=\u001b[39m [\u001b[38;5;241m15\u001b[39m, \u001b[38;5;241m9\u001b[39m, \u001b[38;5;241m1\u001b[39m]\n\u001b[1;32m---> 51\u001b[0m result \u001b[38;5;241m=\u001b[39m \u001b[43mrecover_array\u001b[49m\u001b[43m(\u001b[49m\u001b[43mn\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mb\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mc\u001b[49m\u001b[43m)\u001b[49m\n\u001b[0;32m     52\u001b[0m \u001b[38;5;28mprint\u001b[39m(result)\n",
      "Cell \u001b[1;32mIn[7], line 14\u001b[0m, in \u001b[0;36mrecover_array\u001b[1;34m(n, b, c)\u001b[0m\n\u001b[0;32m     12\u001b[0m             diff2 \u001b[38;5;241m=\u001b[39m val\n\u001b[0;32m     13\u001b[0m         \u001b[38;5;28;01melse\u001b[39;00m:\n\u001b[1;32m---> 14\u001b[0m             \u001b[38;5;28;01mraise\u001b[39;00m \u001b[38;5;167;01mValueError\u001b[39;00m(\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mInvalid input: More than two unique differences found.\u001b[39m\u001b[38;5;124m\"\u001b[39m)\n\u001b[0;32m     16\u001b[0m \u001b[38;5;66;03m# Step 3: Create candidate set\u001b[39;00m\n\u001b[0;32m     17\u001b[0m candidates \u001b[38;5;241m=\u001b[39m []\n",
      "\u001b[1;31mValueError\u001b[0m: Invalid input: More than two unique differences found."
     ]
    }
   ],
   "source": [
    "def recover_array(n, b, c):\n",
    "    # Step 1: Compute the difference between b and c\n",
    "    d = [c[i] - b[i] for i in range(n - 1)]\n",
    "\n",
    "    # Step 2: Find the unique non-zero differences (diff1, diff2)\n",
    "    diff1, diff2 = None, None\n",
    "    for val in d:\n",
    "        if val != 0:\n",
    "            if diff1 is None:\n",
    "                diff1 = val\n",
    "            elif diff2 is None:\n",
    "                diff2 = val\n",
    "            else:\n",
    "                raise ValueError(\"Invalid input: More than two unique differences found.\")\n",
    "\n",
    "    # Step 3: Create candidate set\n",
    "    candidates = []\n",
    "    for x in b + c:  # Concatenate b and c to ensure all elements are considered\n",
    "        candidates.extend([x + diff1, x + diff2])\n",
    "\n",
    "    # Step 4: Identify a_i and a_j from candidates\n",
    "    a_i, a_j = None, None\n",
    "    for i, cand in enumerate(candidates):\n",
    "        for j, other_cand in enumerate(candidates):\n",
    "            if i != j and cand + diff1 == other_cand - diff2:\n",
    "                a_i, a_j = cand, other_cand\n",
    "                break\n",
    "        if a_i is not None and a_j is not None:\n",
    "            break\n",
    "\n",
    "    # Step 5: Recover array a\n",
    "    recovered_a = [0] * n\n",
    "    prefix_sum = 0\n",
    "    for i in range(n - 1):\n",
    "        prefix_sum += b[i]\n",
    "        recovered_a[i] = prefix_sum - b[i]\n",
    "\n",
    "    # Insert a_i and a_j into their respective positions\n",
    "    # Since we don't know the exact indices of a_i and a_j,\n",
    "    # assume they were inserted at the end of the list during recovery\n",
    "    recovered_a[-2], recovered_a[-1] = a_i, a_j\n",
    "\n",
    "    return recovered_a\n",
    "\n",
    "\n",
    "# Example inputs\n",
    "n = 4\n",
    "b = [8, 18, 14]\n",
    "c = [15, 9, 1]\n",
    "\n",
    "result = recover_array(n, b, c)\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_a(n, b, c):\n",
    "    b = [0] + b\n",
    "    c = [0] + c\n",
    "    d = [0] * (n + 1)\n",
    "    for i in range(1, n + 1):\n",
    "        d[i] = b[i] - b[i - 1]\n",
    "    e = [0] * (n + 1)\n",
    "    for i in range(1, n + 1):\n",
    "        e[i] = c[i] - c[i - 1]\n",
    "    f = [0] * (n + 1)\n",
    "    for i in range(1, n + 1):\n",
    "        f[i] = d[i] - e[d[i]]\n",
    "    g = [0] * (n + 1)\n",
    "    for i in range(1, n + 1):\n",
    "        g[i] = e[f[i]]\n",
    "    h = [0] * (n + 1)\n",
    "    for i in range(1, n + 1):\n",
    "        h[i] = f[g[i]]\n",
    "    j = n\n",
    "    k = h.index(j)\n",
    "    a = []\n",
    "    while k != j:\n",
    "        a.append(k)\n",
    "        j = h[k]\n",
    "        k = a.index(j)\n",
    "    return a\n",
    "\n",
    "n = int(input())\n",
    "b = list(map(int, input().split()))\n",
    "c = list(map(int, input().split()))\n",
    "print(' '.join(map(str, find_a(n, b, c))))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
